/*
7-1 链表去重（25 分）提问
	给定一个带整数键值的链表 L，你需要把其中绝对值重复的键值结点删掉。即对每个键值 K，只有第一个绝对值等于 K 的结点被保留。同时，所有被删除的结点须被保存在另一个链表上。例如给定 L 为 21→-15→-15→-7→15，你需要输出去重后的链表 21→-15→-7，还有被删除的链表 -15→15。

	输入格式：
	输入在第一行给出 L 的第一个结点的地址和一个正整数 N（≤10​5​​ ，为结点总数）。一个结点的地址是非负的 5 位整数，空地址 NULL 用 -1 来表示。

	随后 N 行，每行按以下格式描述一个结点：

	地址 键值 下一个结点
	其中地址是该结点的地址，键值是绝对值不超过10 ​4
	​​ 的整数，下一个结点是下个结点的地址。

	输出格式：
	首先输出去重后的链表，然后输出被删除的链表。每个结点占一行，按输入的格式输出。

	输入样例：
	00100 5
	99999 -7 87654
	23854 -15 00000
	87654 15 -1
	00000 -15 99999
	00100 21 23854
	输出样例：
	00100 21 23854
	23854 -15 99999
	99999 -7 -1
	00000 -15 87654
	87654 15 -1
*/

#include <iostream>
#include <math.h>
using namespace std;
struct MagicalList
{
	int beginAdd;
	int value;
	int endAdd;
	MagicalList *next;
};
int main()
{
	int firstAddress, n, i, j, temp;
	scanf("%d%d", &firstAddress, &n);
	MagicalList * mList = new MagicalList[100100], *allList;
	//把用神奇输入方式输入的链表  抽取成  正常链表
	for(i = 0; i < n; i++)
	{
		scanf("%d", &temp);
		mList[temp].beginAdd = temp;
		scanf("%d%d", &mList[temp].value, &mList[temp].endAdd);
		if(firstAddress == temp)
			allList = &mList[temp];
		if(mList[temp].endAdd == -1)
			mList[temp].next = NULL;
		else
			mList[temp].next = &mList[mList[temp].endAdd];
	}

	int arr[10010] = {0};
	MagicalList *tempa = allList;
	allList = tempa;
	//存储临时的两只链表
	MagicalList *newList = new MagicalList, *delList = new MagicalList;
	newList->next = delList->next = NULL;
	//两只链表的头
	MagicalList *headNew = newList, *headDel = delList, *q;
	while(allList != NULL)
	{
		q = allList;
		allList = allList->next;
		q->next = NULL;
		if(arr[abs(q->value)] == 0)
		{
			newList->next = q;
			newList = newList->next;
			arr[abs(q->value)] = 1;
		}
		else
		{
			delList->next = q;
			delList = delList->next;
		}
	}
	headNew = headNew->next;
	while(headNew)
	{
		if(headNew->next == NULL)
		{
			printf("%05d %d -1\n", headNew->beginAdd, headNew->value);
			break;
		}
		else
			headNew->endAdd = headNew->next->beginAdd;
		printf("%05d %d %05d\n", headNew->beginAdd, headNew->value, headNew->endAdd);
		headNew = headNew->next;
	}
	headDel = headDel->next;
	while(headDel)
	{
		if(headDel->next == NULL)
		{
			printf("%05d %d -1\n", headDel->beginAdd, headDel->value);
			break;
		}
		else
			headDel->endAdd = headDel->next->beginAdd;
		printf("%05d %d %05d\n", headDel->beginAdd, headDel->value, headDel->endAdd);
		headDel = headDel->next;
	}
	return 0;
}